%!TEX root = main.tex

\section{Related Work}\label{sec:Related-Work}
%\subsection{Search on Social Media Platform}
\noindent\textbf{Search on Social Media Platform.}
Facebook developed Unicorn \cite{Facebook:Unicorn} to
handle large-scale query processing. While it supports socially related
search, the feature is only available for predefined entities rather
than for arbitrary documents. Moreover, Unicorn is built on
list operators like \textit{LISTAND} and \textit{LISTOR} to merge search results.
This can be very costly especially for real time search
because the search space is huge. Twitter's
real time query engine, Earlybird \cite{Twitter:Earlybird}, has also been
reported to offer high throughput query evaluation for
fast rate of incoming tweets. Unfortunately, it fails to consider
social relationship. Therefore, our proposed method can
complement existing engines by efficiently handling
real time search with social relevance.

\Comment{
\subsection{Real Time Search Index on Social Network}
Several research work have been devoted to develop real time search indices over the social networks. Chen et al. \cite{NUS:TI} proposed TI to enable instant keyword search for Twitter. TI takes text similarity, tweet popularity and freshness to rank the tweets. However, TI does not consider social relevance, thus queries are processed in the global scale instead of customized search for the query user. Therefore the index employed by TI cannot be directly applied to social search in our case. In \cite{ProvenanceDiscovery}, authors presented an index to manage the microblog messages and explore the provenance of a message being transformed over the network. the query model takes care of time relevance and topic provenance. Like TI, the index fails to offer the social relevance feature. Our proposed query model will include social relevance feature on top of existing real time indices and narrow down the research gap.

\subsection{Personalized Search on Social Tagging Network}
 On social tagging network, users are free to annotate documents with freely chosen keywords. By leveraging relationship exhibits in direct social links and tagging behaviours, several personalized search techniques have been proposed \cite{PersonSearch:Schenkel:2008:SIGIR,PersonSearch:Sihem:2008:VLDB,PersonSearch:Silviu:2013:CIKM}. However, existing approaches rely on static inverted lists and usually sort the documents by keyword frequencies to perform efficient pruning. These indices cannot handle high rate of documents ingestion because maintaining sorted lists in terms of keyword frequencies requires huge number of random I/O. The existing indices should be re-designed to deal with the extra time dimension and the new structure should take into consideration of both efficient search and fast update. In this paper, we devised an efficient index and search algorithm which concurrently customized for all query dimensions: text similarity, time closeness and social relevance.
}

\vspace{1mm}
%\subsection{Search on Social Network}
\noindent\textbf{Search on Social Network.}
Several research works have been proposed for real time search indices over the social networks. Chen et al.
introduced a partial index named TI to enable instant keyword search for Twitter \cite{NUS:TI}. Yao et al. devised an index to search for the microblog messages which are ranked by their provenance in the network \cite{ProvenanceDiscovery}. However, none of them offers customized search for the query user. Although indices on social tagging network offer the social relevance feature \cite{PersonSearch:Schenkel:2008:SIGIR,PersonSearch:Sihem:2008:VLDB,PersonSearch:Silviu:2013:CIKM}, existing approaches rely on static inverted lists that sort documents by keyword frequencies to perform efficient pruning. These indices cannot handle high rate of documents ingestion because maintaining sorted lists w.r.t keyword frequencies requires huge number of random I/Os.
Thus, there is a need to design novel indices that are update-efficient
and support efficient search with social relevance feature.


\vspace{1mm}
%\subsection{Distance Indices on Social Network}
\noindent\textbf{Distance Indices on Social Networks.}
%We studied two closely related problems: distance query on road networks and social networks.
Road network distance query has been well studied in \cite{RoadNetwork:Rocha-Junior:2012:EDBT,RoadNetwork:Zhong:2013:CIKM,RoadNetwork:Ken:2012:TKDE}. However, they cannot work on large social networks because the vertex degree in road networks is generally constant but dynamic in social networks due to the \textbf{power law} property. Existing distance indices for
social networks \cite{TEDI:Fang:SIGMOD:2011,PrunedLable:Akiba:SIGMOD:2013,Agarwal:2012:SPL:2342549.2342559,Cheng:VertexCover} cannot be applied to our
scenario for several reasons.
First, the schemes in \cite{TEDI:Fang:SIGMOD:2011,PrunedLable:Akiba:SIGMOD:2013,Agarwal:2012:SPL:2342549.2342559} assume
un-weighted graphs and are not able to handle weighted graphs.
Second, the mechanisms in
\cite{TEDI:Fang:SIGMOD:2011,PrunedLable:Akiba:SIGMOD:2013} are
only efficient for social graphs with low tree-width property.
Unfortunately, as reported in \cite{TreeWidth},
the low tree width property does not hold in real world social graphs.
We also made this observation in our real datasets.
Lastly, personalized top-k query requires one-to-many distance query
whereas the methods in
\cite{Agarwal:2012:SPL:2342549.2342559,PrunedLable:Akiba:SIGMOD:2013}
are applicable only for one-to-one query and the solution in
\cite{Cheng:VertexCover} only supports
one-to-all query. It is hard to extend these schemes
to fit our case. It therefore motivates us to design pruning methods to overcome the distance query problem on large social networks.
